In many real-life situations, we are interested in the value of a physical quantity y that is difficult or impossible to measure directly. To estimate y, we find some easier-to-measure quantities x1, … , xn which are related to y by a known relation y = f. Measurements are never 100% accurate; hence, the measured values equation image are different from xi, and the resulting estimate equation image is different from the desired value y = f. How different can it (...) be? Traditional engineering approach to error estimation in data processing assumes that we know the probabilities of different measurement errors equation image. In many practical situations, we only know the upper bound Δi for this error; hence, after the measurement, the only information that we have about xi is that it belongs to the interval equation image. In this case, it is important to find the range y of all possible values of y = f when xi ∈ xi. We start the paper with a brief overview of the computational complexity of the corresponding interval computation problems: Most of the related problems turn out to be, in general, at least NP-hard. In this paper, we show how the use of quantum computing can speed up some computations related to interval and probabilistic uncertainty. We end the paper with speculations on whether “hypothetic” physical devices can compute NP-hard problems faster than in exponential time. Most of the paper's results were first presented at NAFIPS'2003 [30]. (shrink)

This book provides a general survey of the main concepts, questions and results that have been developed in the recent interactions between quantum information, quantum computation and logic. Divided into 10 chapters, the books starts with an introduction of the main concepts of the quantum-theoretic formalism used in quantum information. It then gives a synthetic presentation of the main “mathematical characters” of the quantum computational game: qubits, quregisters, mixtures of quregisters, quantum logical gates. (...) Next, the book investigates the puzzling entanglement-phenomena and logically analyses the Einstein–Podolsky–Rosen paradox and introduces the reader to quantum computational logics, and new forms of quantum logic. The middle chapters investigate the possibility of a quantum computational semantics for a language that can express sentences like “Alice knows that everybody knows that she is pretty”, explore the mathematical concept of quantum Turing machine, and illustrate some characteristic examples that arise in the framework of musical languages. The book concludes with an analysis of recent discussions, and contains a Mathematical Appendix which is a survey of the definitions of all main mathematical concepts used in the book. (shrink)

While probabilistic logics in principle might be applied to solve a range of problems, in practice they are rarely applied --- perhaps because they seem disparate, complicated, and computationally intractable. This programmatic book argues that several approaches to probabilistic logic fit into a simple unifying framework in which logically complex evidence is used to associate probability intervals or probabilities with sentences. Specifically, Part I shows that there is a natural way to present a question posed in (...) class='Hi'>probabilistic logic, and that various inferential procedures provide semantics for that question, while Part II shows that there is the potential to develop computationally feasible methods to mesh with this framework. The book is intended for researchers in philosophy, logic, computer science and statistics. A familiarity with mathematical concepts and notation is presumed, but no advanced knowledge of logic or probability theory is required. (shrink)

In this paper we solve the problem how to axiomatize a system of quantum computational gates known as the Poincaré irreversible quantum computational system. A Hilbert-style calculus is introduced obtaining a strong completeness theorem.

While in principle probabilistic logics might be applied to solve a range of problems, in practice they are rarely applied at present. This is perhaps because they seem disparate, complicated, and computationally intractable. However, we shall argue in this programmatic paper that several approaches to probabilistic logic into a simple unifying framework: logically complex evidence can be used to associate probability intervals or probabilities with sentences.

We establish a connection between measurement-based quantum computation and the field of mathematical logic. We show that the computational power of an important class of quantum states called graph states, representing resources for measurement-based quantum computation, is reflected in the expressive power of (classical) formal logic languages defined on the underlying mathematical graphs. In particular, we show that for all graph state resources which can yield a computational speed-up with respect to classical computation, the (...) underlying graphs—describing the quantum correlations of the states—are associated with undecidable logic theories. Here undecidability is to be interpreted in a sense similar to Gödel’s incompleteness results, meaning that there exist propositions, expressible in the above classical formal logic, which cannot be proven or disproven. (shrink)

In this paper we show the embedding of Hybrid Probabilistic Logic Programs into the rather general framework of Residuated Logic Programs, where the main results of (definite) logic programming are validly extrapolated, namely the extension of the immediate consequences operator of van Emden and Kowalski. The importance of this result is that for the first time a framework encompassing several quite distinct logic programming semantics is described, namely Generalized Annotated Logic Programs, Fuzzy Logic Programming, Hybrid Probabilistic Logic Programs, (...) and Possibilistic Logic Programming. Moreover, the embedding provides a more general semantical structure paving the way for defining paraconsistent probabilistic reasoning with a logic programming semantics. (shrink)

There is a well-documented paradigm-shift in eighteenth century Jesuit philosophy and science, at the very least in Central Europe: traditional scholastic version(s) of Aristotelianism were replaced by early modern rationalism (Wolff's systematisation of Leibnizian philosophy) and early modern science and mathematics. In the field of probability, this meant that the traditional Jesuit engagement with probability, uncertainty, and truthlikeness (in particular, as applied to moral theology) could translate into mathematical language, and can be analysed against the background of the accounts of (...) probability, pre-mathematical Jesuit logic, Wolff's conceptual analysis, and Bernoullian mathematisation. The works of two Jesuit philosophers, Berthold Hauser and Sigismund Storchenau, can be related to this context. The core of their logic of (epistemic) probability is the account of negation (or ‘contradiction’) and implication (or ‘argument’), in particular, the algorithms for computing the reliability of one piece of evidence when compared to the respective counter-evidence and for computing the probability of a conclusion given the probability of its premises. (shrink)

An experimental realization of quantum computers is composed of two or more calcium ions trapped in a magnetic quadripole. Information is transferred to and read from the ions by means of structured lasers that interact with the ions’ vibration pattern, causing changes of energy distribution in their electronic structure. Departing from an initial state when the ions are cooled, the use of lasers modifies the internal state of one ion that is entangled with the others, then changing the collective (...) states. In such quantum computers, some of the physically possible electronic states are avoided or not taken into consideration, to force the system to work as a binary device. In this essay, we discuss the dynamics that the ions could spontaneously display and its possible implications for the principles of computational logics. (shrink)

Tasked with the challenge to build better and better computers, quantum computing and classical computing face the same conundrum: the success of classical computing systems. Small quantum computing systems have been demonstrated, and intermediate-scale systems are on the horizon, capable of calculating numeric results or simulating physical systems far beyond what humans can do by hand. However, to be commercially viable, they must surpass what our wildly successful, highly advanced classical computers can already do. At the same time, (...) those classical computers continue to advance, but those advances are now constrained by thermodynamics, and will soon be limited by the discrete nature of atomic matter and ultimately quantum effects. Technological advances benefit both quantum and classical machinery, altering the competitive landscape. Can we build quantum computing systems that out-compute classical systems capable of some $10^{30}$ logic gates per month? This article will discuss the interplay in these competing and cooperating technological trends. (shrink)

The nature of quantum computation is discussed. It is argued that, in terms of the amount of information manipulated in a given time, quantum and classical computation are equally efficient. Quantum superposition does not permit quantum computers to ''perform many computations simultaneously'' except in a highly qualified and to some extent misleading sense. Quantum computation is therefore not well described by interpretations of quantum mechanics which invoke the concept of vast numbers (...) of parallel universes. Rather, entanglement makes available types of computation processes which, while not exponentially larger than classical ones, are unavailable to classical systems. The essence of quantum computation is that it uses entanglement to generate and manipulate a physical representation of the correlations between logical entities, without the need to completely represent the logical entities themselves. (shrink)

The aim of this paper is to state the single most powerful argument for use of a non-classical logic in quantum mechanics. In outline the argument is the following. The working logic of a science is the logic of the events and propositions to which probabilities are assigned. A probability should be assigned to every element of the algebra of events. In the case of quantum mechanics probabilities may be assigned to events but not, without restriction, to the (...) conjunction of two events. The conclusion is that the working logic of quantum mechanics is not classical. The nature of the logic that is appropriate for quantum mechanics is examined. (shrink)

Though there is yet no consensus on the right way to understand ‘physicalism’, most philosophers agree that, regardless of whatever else is required, physicalism cannot be true if there exists fundamental mentality. I will follow Jessica Wilson (Philosophical Studies 131:61–99, 2006) in calling this the 'No Fundamental Mentality' (NFM) constraint on physicalism. Unfortunately for those who wish to constrain physicalism in this way, NFM admits of a counterexample: an artificially intelligent quantum computer which employs quantum properties as part (...) of its cognitive operations. If one of these quantum properties serves a proper functional role in the artificial intelligence, then that property counts as a mental under the physicalism-friendly theory of mentality called “realizer functionalism”, which says that a lower-order property is mental if it satisfies an appropriate higher-order functional description. Further, if this quantum property is both fundamental and mental, then NFM must rule that it is not physical. Yet the existence of such an artificially intelligent quantum computer, which possesses mental properties solely in virtue of the functional roles those properties play, is surely consistent with the truth of physicalism. This ought to motivate NFM proponents to reformulate their view. (shrink)

In this paper we present a probabilistic notion of entailment for finite sets of premises, which has classical entailment as a special case, and show that it is well defined; i.e., that the problem of whether a sentence is entailed by a set of premises is computable. Further we present a natural deductive system and prove that it is the strongest deductive system possible without referring to probabilities.

The potential for scalable quantum computing depends on the viability of fault tolerance and quantum error correction, by which the entropy of environmental noise is removed during a quantum computation to maintain the physical reversibility of the computer’s logical qubits. However, the theory underlying quantum error correction applies a linguistic double standard to the words “noise” and “measurement” by treating environmental interactions during a quantum computation as inherently reversible, and environmental interactions at the (...) end of a quantum computation as irreversible measurements. Specifically, quantum error correction theory models noise as interactions that are uncorrelated or that result in correlations that decay in space and/or time, thus embedding no permanent information to the environment. I challenge this assumption both on logical grounds and by discussing a hypothetical quantum computer based on “position qubits.” The technological difficulties of producing a useful scalable position-qubit quantum computer parallel the overwhelming difficulties in performing a double-slit interference experiment on an object comprising a million to a billion fermions. (shrink)

We present two approaches to investigate the validity of connexive principles and related formulas and properties within coherence-based probability logic. Connexive logic emerged from the intuition that conditionals of the formif not-A,thenA, should not hold, since the conditional’s antecedentnot-Acontradicts its consequentA. Our approaches cover this intuition by observing that the only coherent probability assessment on the conditional event$${A| \overline{A}}$$A|A¯is$${p(A| \overline{A})=0}$$p(A|A¯)=0. In the first approach we investigate connexive principles within coherence-based probabilistic default reasoning, by interpreting defaults and negated defaults in (...) terms of suitable probabilistic constraints on conditional events. In the second approach we study connexivity within the coherence framework of compound conditionals, by interpreting connexive principles in terms of suitable conditional random quantities. After developing notions of validity in each approach, we analyze the following connexive principles:Aristotle’s theses,Aristotle’s Second Thesis,Abelard’s First Principle, andBoethius’ theses. We also deepen and generalize some principles and investigate further properties related to connexive logic (likenon-symmetry). Both approaches satisfyminimalrequirements for a connexive logic. Finally, we compare both approaches conceptually. (shrink)

The aim of this paper is to present some basic notions of the theory of quantum computing and to compare them with the basic notions of the classical theory of computation. I am convinced, that the results of quantum computation theory (QCT) are not only interesting in themselves, but also should be taken into account in discussions concerning the nature of mathematical knowledge. The philosophical discussion will however be postponed to another paper. QCT seems not to (...) be well-known among philosophers (at least not to the degree it deserves), so the aim of this paper is to provide the necessary technical preliminaries presented in a way accessible to the general philosophical audience. (shrink)

In the article, the philosophical significance of quantum computation theory for philosophy of mathematics is discussed. In particular, I examine the notion of “quantum-assisted proof” (QAP); the discussion sheds light on the problem of the nature of mathematical proof; the potential empirical aspects of mathematics and the realism-antirealism debate (in the context of the indispensability argument). I present a quasi-empiricist account of QAP’s, and discuss the possible impact on the discussions centered around the Enhanced Indispensabity Argument (EIA).

It is argued that suitably trained neural language models exhibit key properties of epistemic agency: they hold probabilistically coherent and logically consistent degrees of belief, which they can rationally revise in the face of novel evidence. To this purpose, we conduct computational experiments with rankers: T5 models [Raffel et al. 2020] that are pretrained on carefully designed synthetic corpora. Moreover, we introduce a procedure for eliciting a model’s degrees of belief, and define numerical metrics that measure the extent to which (...) given degrees of belief violate (probabilistic, logical, and Bayesian) rationality constraints. While pretrained rankers are found to suffer from global inconsistency (in agreement with, e.g., [Jang et al. 2021]), we observe that subsequent self-training on auto-generated texts allows rankers to gradually obtain a probabilistically coherent belief system that is aligned with logical constraints. In addition, such self-training is found to have a pivotal role in rational evidential learning, too, for it seems to enable rankers to propagate a novel evidence item through their belief systems, successively re-adjusting individual degrees of belief. All this, we conclude, confirms the Rationality Hypothesis, i.e., the claim that suitable trained NLMs may exhibit advanced rational skills. We suggest that this hypothesis has empirical, yet also normative and conceptual ramifications far beyond the practical linguistic problems NLMs have originally been designed to solve. (shrink)

The paper addresses Leon Hen.kin's proposition as a " lighthouse", which can elucidate a vast territory of knowledge uniformly: logic, set theory, information theory, and quantum mechanics: Two strategies to infinity are equally relevant for it is as universal and t hus complete as open and thus incomplete. Henkin's, Godel's, Robert Jeroslow's, and Hartley Rogers' proposition are reformulated so that both completeness and incompleteness to be unified and thus reduced as a joint property of infinity and of all infinite (...) sets. However, only Henkin's proposition equivalent to an internal position to infinity is consistent . This can be retraced back to set theory and its axioms, where that of choice is a key. Quantum mechanics is forced to introduce infinity implicitly by Hilbert space, on which is founded its formalism. One can demonstrate that some essential properties of quantum information, entanglement, and quantum computer originate directly from infinity once it is involved in quantum mechanics. Thus, these phenomena can be elucidated as both complete and incomplete, after which choice is the border between them. A special kind of invariance to the axiom of choice shared by quantum mechanics is discussed to be involved that border between the completeness and incompleteness of infinity in a consistent way. The so-called paradox of Albert Einstein, Boris Podolsky, and Nathan Rosen is interpreted entirely in the same terms only of set theory. Quantum computer can demonstrate especially clearly the privilege of the internal position, or " observer'' , or "user" to infinity implied by Henkin's proposition as the only consistent ones as to infinity. An essential area of contemporary knowledge may be synthesized from a single viewpoint. (shrink)

The equivalence principle, being one of the building blocks of general relativity, seems to be crucial for analysis of quantum effects in gravity. In this paper we consider the relation between the equivalence principle and the consistency of quantum information processing in gravitational field. We propose an analysis with a looped evolution consisting of steps both in the gravitational field and in the accelerated reference frame. We show that without the equivalence principle the looped quantum evolution cannot (...) be unitary and looses its consistency. For this reasoning the equivalence principle is formulated in terms of the gauge transformations and is analyzed for particles acquiring an appropriate phase associated with the action over the looped path. In consequence, to keep consistency of quantum operations in gravitational field, it is required to keep a quantum variant of the equivalence principle. This proves importance of the quantized version of this fundamental gravitational principle for quantum information processing. (shrink)

The logic of a physical system consists of the elementary observables of the system. We show that for chaotic systems the logic is not any more the classical Boolean lattice but a kind of fuzzy logic which we characterize for a class of chaotic maps. Among other interesting properties the fuzzy logic of chaos does not allow for infinite combinations of propositions. This fact reflects the instability of dynamics and it is shared also by quantum systems with diagonal singularity. (...) We also generalize the fuzzy implication to a probabilistic implication following the hint of von Neumann. In this way we can evaluate the probability of the validity of the logical inference. (shrink)

We show how to obtain a probabilistic semantics and calculus for a logic presented by a valuation specification. By identifying general forms of valuation constraints we are able to accommodate a wide class of propositional based logics encompassing multi-valued logics like Łukasiewicz 3-valued logic and the Belnap–Dunn four-valued logic as well as paraconsistent logics like $${\textsf{mbC}}$$ and $${\textsf{LFI1}}$$. The probabilistic calculus is automatically generated from the valuation specification. Although not having explicit probability constructors in the (...) language, the rules of the calculus reflect the valuation constraints in a probabilistic way. Indeed the probability of the premises of each rule coincides with the probability of the conclusions. Moreover, a failed exhaustive attempt of proving a formula in this calculus means non-derivability. Nevertheless when the non-derived formula is consistent then it is possible to extract a satisfying valuation from the failed exhaustive attempt. Soundness and completeness of the calculi are established with respect to the probabilistic semantics consisting of probability spaces also induced by the valuation specification. Furthermore we prove the equivalence between the probabilistic and the valuation semantics. (shrink)

As Classical Propositional Logic finds its algebraic counterpart in Boolean algebras, the logic of Quantum Mechanics, as outlined within G. Birkhoff and J. von Neumann’s approach to Quantum Theory (Birkhoff and von Neumann in Ann Math 37:823–843, 1936) [see also (Husimi in I Proc Phys-Math Soc Japan 19:766–789, 1937)] finds its algebraic alter ego in orthomodular lattices. However, this logic does not incorporate time dimension although it is apparent that the propositions occurring in the logic of Quantum (...) Mechanics are depending on time. The aim of the present paper is to show that tense operators can be introduced in every logic based on a complete lattice, in particular in the logic of quantum mechanics based on a complete orthomodular lattice. If the time set is given together with a preference relation, we introduce tense operators in a purely algebraic way. We derive several important properties of such operators, in particular we show that they form dynamic pairs and, altogether, a dynamic algebra. We investigate connections of these operators with logical connectives conjunction and implication derived from Sasaki projections in an orthomodular lattice. Then we solve the converse problem, namely to find for given time set and given tense operators a time preference relation in order that the resulting time frame induces the given operators. We show that the given operators can be obtained as restrictions of operators induced by a suitable extended time frame. (shrink)

We argue that there is a simple, unique, reason for all quantum paradoxes, and that such a reason is not uniquely related to quantum theory. It is rather a mathematical question that arises at the intersection of logic, probability, and computation. We give our ‘weirdness theorem’ that characterises the conditions under which the weirdness will show up. It shows that whenever logic has bounds due to the algorithmic nature of its tasks, then weirdness arises in the special (...) form of negative probabilities or non-classical evaluation functionals. Weirdness is not logical inconsistency, however. It is only the expression of the clash between an unbounded and a bounded view of computation in logic. We discuss the implication of these results for quantum mechanics, arguing in particular that its interpretation should ultimately be computational rather than exclusively physical. We develop in addition a probabilistic theory in the real numbers that exhibits the phenomenon of entanglement, thus concretely showing that the latter is not specific to quantum mechanics. (shrink)

A probabilistic propositional logic, endowed with a constructor for asserting compatibility of diagonalisable and bounded observables, is presented and illustrated for reasoning about the random results of projective measurements made on a given quantum state. Simultaneous measurements are assumed to imply that the underlying observables are compatible. A sound and weakly complete axiomatisation is provided relying on the decidable first-order theory of real closed ordered fields. The proposed logic is proved to be a conservative extension of classical propositional (...) logic. (shrink)

In this transdisciplinary article which stems from philosophical considerations (that depart from phenomenology—after Merleau-Ponty, Heidegger and Rosen—and Hegelian dialectics), we develop a conception based on topological (the Moebius surface and the Klein bottle) and geometrical considerations (based on torsion and non-orientability of manifolds), and multivalued logics which we develop into a unified world conception that surmounts the Cartesian cut and Aristotelian logic. The role of torsion appears in a self-referential construction of space and time, which will be further related (...) to the commutator of the True and False operators of matrix logic, still with a quantum superposed state related to a Moebius surface, and as the physical field at the basis of Spencer-Brown’s primitive distinction in the protologic of the calculus of distinction. In this setting, paradox, self-reference, depth, time and space, higher-order non-dual logic, perception, spin and a time operator, the Klein bottle, hypernumbers due to Musès which include non-trivial square roots of ±1 and in particular non-trivial nilpotents, quantum field operators, the transformation of cognition to spin for two-state quantum systems, are found to be keenly interwoven in a world conception compatible with the philosophical approach taken for basis of this article. The Klein bottle is found not only to be the topological in-formation for self-reference and paradox whose logical counterpart in the calculus of indications are the paradoxical imaginary time waves, but also a classical-quantum transformer (Hadamard’s gate in quantum computation) which is indispensable to be able to obtain a complete multivalued logical system, and still to generate the matrix extension of classical connective Boolean logic. We further find that the multivalued logic that stems from considering the paradoxical equation in the calculus of distinctions, and in particular, the imaginary solutions to this equation, generates the matrix logic which supersedes the classical logic of connectives and which has for particular subtheories fuzzy and quantum logics. Thus, from a primitive distinction in the vacuum plane and the axioms of the calculus of distinction, we can derive by incorporating paradox, the world conception succinctly described above. (shrink)

The intuition guiding the de…nition of computation has shifted over time, a process that is re‡ected in the changing formulations of the Church-Turing thesis. The theory of computation began with logic and gradually moved to the capacity of …nite automata. Consequently, modern computer models rely on general physical principles, with quantum computers representing the extreme case. The paper discusses this development, and the challenges to the Church-Turing thesis in its physical form, in particular, Kieu’s quantum computer (...) and relativistic hyper-computation. Finally, the robustness of the boundary between polynomial and exponential time complexity is considered in connection with quantum computers and quantum information theory. (shrink)

As Classical Propositional Logic finds its algebraic counterpart in Boolean algebras, the logic of Quantum Mechanics, as outlined within G. Birkhoff and J. von Neumann’s approach to Quantum Theory (Birkhoff and von Neumann in Ann Math 37:823–843, 1936) [see also (Husimi in I Proc Phys-Math Soc Japan 19:766–789, 1937)] finds its algebraic alter ego in orthomodular lattices. However, this logic does not incorporate time dimension although it is apparent that the propositions occurring in the logic of Quantum (...) Mechanics are depending on time. The aim of the present paper is to show that tense operators can be introduced in every logic based on a complete lattice, in particular in the logic of quantum mechanics based on a complete orthomodular lattice. If the time set is given together with a preference relation, we introduce tense operators in a purely algebraic way. We derive several important properties of such operators, in particular we show that they form dynamic pairs and, altogether, a dynamic algebra. We investigate connections of these operators with logical connectives conjunction and implication derived from Sasaki projections in an orthomodular lattice. Then we solve the converse problem, namely to find for given time set and given tense operators a time preference relation in order that the resulting time frame induces the given operators. We show that the given operators can be obtained as restrictions of operators induced by a suitable extended time frame. (shrink)

Samson Abramsky’s wide-ranging contributions to logical and structural aspects of Computer Science have had a major influence on the field. This book is a rich collection of papers, inspired by and extending Abramsky’s work. It contains both survey material and new results, organised around six major themes: domains and duality, game semantics, contextuality and quantum computation, comonads and descriptive complexity, categorical and logical semantics, and probabilistic computation. These relate to different stages and aspects of Abramsky’s work, (...) reflecting its exceptionally broad scope and his ability to illuminate and unify diverse topics. Chapters in the volume include a review of his entire body of work, spanning from philosophical aspects to logic, programming language theory, quantum theory, economics and psychology, and relating it to a theory of unification of sciences using dual adjunctions. The section on game semantics shows how Abramsky’s work has led to a powerful new paradigm for the semantics of computation. The work on contextuality and categorical quantum mechanics has been highly influential, and provides the foundation for increasingly widely used methods in quantum computing. The work on comonads and descriptive complexity is building bridges between currently disjoint research areas in computer science, relating Structure to Power. The volume also includes a scientific autobiography, and an overview of the contributions. The outstanding set of contributors to this volume, including both senior and early career academics, serve as testament to Samson Abramsky’s enduring influence. It will provide an invaluable and unique resource for both students and established researchers. (shrink)

Linear temporal logic is a widely used method for verification of model checking and expressing the system specifications. The relationship between theory of automata and logic had a great influence in the computer science. Investigation of the relationship between quantum finite automata and linear temporal logic is a natural goal. In this paper, we present a construction of quantum finite automata on finite words from linear-time temporal logic formulas. Further, the relation between quantum finite automata and linear (...) temporal logic is explored in terms of language recognition and acceptance probability. We have shown that the class of languages accepted by quantum finite automata are definable in linear temporal logic, except for measure-once one-way quantum finite automata. (shrink)

Quantum physics is a linear theory, so it is somewhat puzzling that it can underlie very complex systems such as digital computers and life. This paper investigates how this is possible. Physically, such complex systems are necessarily modular hierarchical structures, with a number of key features. Firstly, they cannot be described by a single wave function: only local wave functions can exist, rather than a single wave function for a living cell, a cat, or a brain. Secondly, the (...) class='Hi'>quantum to classical transition is characterised by contextual wave-function collapse shaped by macroscopic elements that can be described classically. Thirdly, downward causation occurs in the physical hierarchy in two key ways: by the downward influence of time dependent constraints, and by creation, modification, or deletion of lower level elements. Fourthly, there are also logical modular hierarchical structures supported by the physical ones, such as algorithms and computer programs, They are able to support arbitrary logical operations, which can influence physical outcomes as in computer aided design and 3-d printing. Finally, complex systems are necessarily open systems, with heat baths playing a key role in their dynamics and providing local arrows of time that agree with the cosmological direction of time that is established by the evolution of the universe. (shrink)

The epistemic modal auxiliaries must and might are vehicles for expressing the force with which a proposition follows from some body of evidence or information. Standard approaches model these operators using quantificational modal logic, but probabilistic approaches are becoming increasingly influential. According to a traditional view, must is a maximally strong epistemic operator and might is a bare possibility one. A competing account—popular amongst proponents of a probabilisitic turn—says that, given a body of evidence, must \ entails that \\) (...) is high but non-maximal and might \ that \\) is significantly greater than 0. Drawing on several observations concerning the behavior of must, might and similar epistemic operators in evidential contexts, deductive inferences, downplaying and retractions scenarios, and expressions of epistemic tension, I argue that those two influential accounts have systematic descriptive shortcomings. To better make sense of their complex behavior, I propose instead a broadly Kratzerian account according to which must \ entails that \ = 1\) and might \ that \ > 0\), given a body of evidence and a set of normality assumptions about the world. From this perspective, must and might are vehicles for expressing a common mode of reasoning whereby we draw inferences from specific bits of evidence against a rich set of background assumptions—some of which we represent as defeasible—which capture our general expectations about the world. I will show that the predictions of this Kratzerian account can be substantially refined once it is combined with a specific yet independently motivated ‘grammatical’ approach to the computation of scalar implicatures. Finally, I discuss some implications of these results for more general discussions concerning the empirical and theoretical motivation to adopt a probabilisitic semantic framework. (shrink)

Hans Reichenbach’s posthumous book The Direction of Time ends somewhere between Socratic aporia and historical irony. Prompted by Feynman’s diagrammatic formulation of quantum electrodynamics, Reichenbach eventually abandoned the delicate balancing between the macroscopic foundation of the direction of time and microscopic descriptions of time order undertaken throughout the previous chapters in favor of an exclusively macroscopic theory that he had vehemently rejected in the 1920s. I analyze Reichenbach’s reasoning against the backdrop of the history of Feynman diagrams and the (...) current practice of particle physics. Building upon the debates about processes and conserved quantities between Wesley Salmon and Phil Dowe in the 1990s, and the exchange between Reichenbach and the gestalt theorist Kurt Lewin during the 1920s about topology and genidentity, I investigate whether the aporia about local time order could be avoided by following a strategy that Reichenbach adopted elsewhere in the book and develop a notion of functional genidentity that captures the practice of present-day elementary particle physics and the fact that Feynman diagrams have to be understood in the context of a complex mathematical description of scattering processes. (shrink)

A logical approach to Bell's Inequalities of quantum mechanics has been introduced by Abramsky and Hardy [2]. We point out that the logical Bell's Inequalities of [2] are provable in the probability logic of Fagin, Halpern and Megiddo [4]. Since it is now considered empirically established that quantum mechanics violates Bell's Inequalities, we introduce a modified probability logic, that we call quantum team logic, in which Bell's Inequalities are not provable, and prove a Completeness Theorem for this (...) logic. For this end we generalise the team semantics of dependence logic [7] first to probabilistic team semantics, and then to what we call quantum team semantics. (shrink)

This book provides an interdisciplinary approach to one of the most fascinating and important open questions in science: What is quantum mechanics really talking about? In the last decades quantum mechanics has given rise to a new quantum technological era, a revolution taking place today especially within the field of quantum information processing; which goes from quantum teleportation and cryptography to quantum computation. Quantum theory is probably our best confirmed physical theory. However, (...) in spite of its great empirical effectiveness it stands today still without a universally accepted physical representation that allows us to understand its relation to the world and reality. The novelty of the book comes from the multiple perspectives put forward by top researchers in quantum mechanics, from Europe as well as North and South America, discussing the meaning and structure of the theory of quanta. The book comprises in a balanced manner physical, philosophical, logical and mathematical approaches to quantum mechanics and quantum information. Going from quantum superpositions and entanglement to dynamics and the problem of identity; from quantum logic, computation and quasi-set theory to the category approach and teleportation; from realism and empiricism to operationalism and instrumentalism; the book considers from different angles some of the most intriguing questions in the field. From Buenos Aires to Brussels and Cagliari, from Florence to Florianópolis, the interaction between different groups is reflected in the many different articles. This book is interesting not only to the specialists but also to the general public attempting to get a grasp on some of the most fundamental questions of present quantum physics. (shrink)

This book presents a set of historical recollections on the work of Martin Davis and his role in advancing our understanding of the connections between logic, computing, and unsolvability. The individual contributions touch on most of the core aspects of Davis’ work and set it in a contemporary context. They analyse, discuss and develop many of the ideas and concepts that Davis put forward, including such issues as contemporary satisfiability solvers, essential unification, quantum computing and generalisations of Hilbert’s tenth (...) problem. The book starts out with a scientific autobiography by Davis, and ends with his responses to comments included in the contributions. In addition, it includes two previously unpublished original historical papers in which Davis and Putnam investigate the decidable and the undecidable side of Logic, as well as a full bibliography of Davis’ work. As a whole, this book shows how Davis’ scientific work lies at the intersection of computability, theoretical computer science, foundations of mathematics, and philosophy, and draws its unifying vision from his deep involvement in Logic. (shrink)

This book constitutes the strictly refereed post-workshop proceedings of the 11th International Workshop on Computer Science Logic, CSL '97, held as the 1997 Annual Conference of the European Association on Computer Science Logic, EACSL, in Aarhus, Denmark, in August 1997. The volume presents 26 revised full papers selected after two rounds of refereeing from initially 92 submissions; also included are four invited papers. The book addresses all current aspects of computer science logics and its applications and thus presents the (...) state of the art in the area. (shrink)

Predicates are supposed to slice reality neatly in two halves, one for which the predicate holds, the other for which it fails. Yet far from being razors, predicates tend to be dull knives that mangle reality. If reality is a tomato and predicates are knives, then when these knives divide the tomato, plenty of mush remains unaccounted for. Of course some knives are sharper than others, just as some predicates are less vague than others. “x is water” is certainly sharper (...) than “x is beautiful.” But perfect sharpness, perfect boundaries, and perfect separation seem only to obtain in mathematics. The vagueness inherent in many predicates became particularly evident in the twentieth century. Quantum mechanics, the revival of certain ancient paradoxes, and the philosophy of science all contributed to a growing awareness that vagueness was ineliminable from many predicates. Quantum mechanical superposition seems to allow mutually exclusive simultaneous states. In searching for plausible interpretations of quantum mechanics, some researchers attempted to do away with classical bivalent logic. In its place they substituted multivalent quantum logics. Any logic with more than two values forces its predicates to slice reality into more than two parts. Ancient paradoxes involving heaps and baldness also pointed up the 1 Random Predicate Logic 2.. (shrink)

Open peer commentary on the article “Info-computational Constructivism and Cognition” by Gordana Dodig-Crnkovic. Upshot: Dodig-Crnkovic’s “info-computational constructivism” (IC), as an essential part of a constructivist approach, needs integration with the logical, mathematical and physical evidence coming from quantum field theory (QFT) as the fundamental physics of the emergence of “complex systems” in all realms of natural sciences.

In previous work, we studied four well known systems of qualitative probabilistic inference, and presented data from computer simulations in an attempt to illustrate the performance of the systems. These simulations evaluated the four systems in terms of their tendency to license inference to accurate and informative conclusions, given incomplete information about a randomly selected probability distribution. In our earlier work, the procedure used in generating the unknown probability distribution (representing the true stochastic state of the world) tended to (...) yield probability distributions with moderately high entropy levels. In the present article, we present data charting the performance of the four systems when reasoning in environments of various entropy levels. The results illustrate variations in the performance of the respective reasoning systems that derive from the entropy of the environment, and allow for a more inclusive assessment of the reliability and robustness of the four systems. (shrink)

It is shown how all the major conceptual difficulties of standard (textbook) quantum mechanics, including the two measurement problems and the (supposed) nonlocality that conflicts with special relativity, are resolved in the consistent or decoherent histories interpretation of quantum mechanics by using a modified form of quantum logic to discuss quantum properties (subspaces of the quantum Hilbert space), and treating quantum time development as a stochastic process. The histories approach in turn gives rise to (...) some conceptual difficulties, in particular the correct choice of a framework (probabilistic sample space) or family of histories, and these are discussed. The central issue is that the principle of unicity, the idea that there is a unique single true description of the world, is incompatible with our current understanding of quantum mechanics. (shrink)

A theory of approximation to measurable sets and measurable functions based on the concepts of recursion theory and discrete complexity theory is developed. The approximation method uses a model of oracle Turing machines, and so the computational complexity may be defined in a natural way. This complexity measure may be viewed as a formulation of the average-case complexity of real functions—in contrast to the more restrictive worst-case complexity. The relationship between these two complexity measures is further studied and compared with (...) the notion of the distribution-free probabilistic computation. The computational complexity of the Lebesgue integral of polynomial-time approximable functions is studied and related to the question “FP = ♯P?”. (shrink)

Physicists routinely claim that the fundamental laws of physics are 'time symmetric' or 'time reversal invariant' or 'reversible'. In particular, it is claimed that the theory of quantum mechanics is time symmetric. But it is shown in this paper that the orthodox analysis suffers from a fatal conceptual error, because the logical criterion for judging the time symmetry of probabilistic theories has been incorrectly formulated. The correct criterion requires symmetry between future-directed laws and past-directed laws. This criterion is (...) formulated and proved in detail. The orthodox claim that quantum mechanics is reversible is re-evaluated. The property demonstrated in the orthodox analysis is shown to be quite distinct from time reversal invariance. The view of Satosi Watanabe that quantum mechanics is time asymmetric is verified, as well as his view that this feature does not merely show a de facto or 'contingent' asymmetry, as commonly supposed, but implies a genuine failure of time reversal invariance of the laws of quantum mechanics. The laws of quantum mechanics would be incompatible with a time-reversed version of our universe. (shrink)

This book constitutes the thoroughly refereed post-conference proceedings of the 10th International Conference on Quantum Interaction, QI 2016, held in San Francisco, CA, USA, in July 2016. The 21 papers presented in this book were carefully reviewed and selected from 39 submissions. The papers address topics such as: Fundamentals; Quantum Cognition; Language and Applications; Contextuality and Foundations of Probability; and Quantum-Like Measurements.

Algebraic quantum field theory provides a rigorous analysis of the structure of relativistic quantum mechanics. It is formulated in terms of a net of operator algebras indexed by regions of a Lorentzian manifold. In several cases, this net is represented by a family of von Neumann algebras, specifically, Type III factors. Local quantum field logic emerges as a logical system that captures the propositional structure encoded in the algebras of the net and their respective locality conditions. Specifically, (...) by considering an expanded language of orthomodular lattices that naturally arises from the Murray-von Neumann dimension theory, we first provide equational conditions in the lattice of projectors of a von Neumann factor that uniquely characterize the Type III factor within the Murray-von Neumann classification. This equational system motivates the study of a variety of algebras with an underlying orthomodular lattice structure, which we shall refer to as _LQF_-algebras. A Hilbert-style calculus is also introduced, establishing a completeness theorem with respect to the variety of _LQF_-algebras. (shrink)

First-ever comprehensive introduction to the major new subject of quantum computing and quantum information.

In this paper we present two families of probability logics (denoted _QLP_ and $QLP^{ORT}$ ) suitable for reasoning about quantum observations. Assume that $\alpha$ means “O = a”. The notion of measuring of an observable _O_ can be expressed using formulas of the form $\square \lozenge \alpha$ which intuitively means “if we measure _O_ we obtain $\alpha$ ”. In that way, instead of non-distributive structures (i.e., non-distributive lattices), it is possible to relay on classical logic (...) extended with the corresponding modal laws for the modal logic ${\textbf{B}}$. We consider probability formulas of the form $CS_{z_{1},\rho _{1}; \ldots ; z_{m},\rho _{m}} \square \lozenge \alpha$ related to an observable _O_ and a possible world (vector) _w_: if _a_ is an eigenvalue of _O_, $w_{1}$,..., $w_{m}$ form a base of a closed subspace of the considered Hilbert space which corresponds to eigenvalue _a_, and if _w_ is a linear combination of the basis vectors such that $w=c_{1}\cdot w_{1}+ \cdots + c_{m}\cdot w_{m}$ for some $c_{i}\in {\mathbb {C}}$, then $\Vert c_{1}-z_{1}\Vert \le \rho _{1}$,..., $\Vert c_{m}-z_{m}\Vert \le \rho _{m}$, and the probability of obtaining _a_ while measuring _O_ in the state _w_ is equal to $\Sigma _{i=1}^{m}\Vert c_{i}\Vert ^{2}$. Formulas are interpreted in reflexive and symmetric Kripke models equipped with probability distributions over families of subsets of possible worlds that are orthocomplemented lattices, while for $QLP^{ORT}$ also satisfy ortomodularity. We give infinitary axiomatizations, prove the corresponding soundness and strong completeness theorems, and also decidability for _QLP_-logics. (shrink)